home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 January: Mac OS SDK / Dev.CD Jan 97 SDK2.toast / Development Kits (Disc 2) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc™ Source Code / Utilities / Node.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-08-28  |  9.5 KB  |  431 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        Node.cpp
  3.  
  4.     Contains:    Implementation of Node class, a node in an n-way tree
  5.  
  6.     Owned by:    Reggie Adkins
  7.  
  8.     Copyright:    © 1993-1996 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.  
  12.          <3>     5/24/96    jpa        Fixed header comment.
  13.          <2>     5/24/96    jpa        1.1MRD: Inlined many methods for
  14.                                     smaller/faster code.
  15.  
  16.     To Do:
  17. */
  18.  
  19. #ifndef _NODE_
  20. #include "Node.h"
  21. #endif
  22.  
  23. #ifndef _EXCEPT_
  24. #include "Except.h"
  25. #endif
  26.  
  27. #ifndef _ODDEBUG_
  28. #include "ODDebug.h"
  29. #endif
  30.  
  31.  
  32. #pragma segment ODNode
  33.  
  34. //======================================================================================
  35. // Class Node
  36. //======================================================================================
  37.  
  38. //------------------------------------------------------------------------------
  39. // Node::Node
  40. //
  41. // Description
  42. //------------------------------------------------------------------------------
  43.  
  44. Node::Node() 
  45. {
  46.     fParent = kODNULL; 
  47. }
  48.  
  49. //------------------------------------------------------------------------------
  50. // Node::~Node
  51. //
  52. // Description
  53. //------------------------------------------------------------------------------
  54.  
  55. Node::~Node() 
  56. {
  57. }
  58.  
  59. //------------------------------------------------------------------------------
  60. // Node::Size
  61. //
  62. // Description
  63. //------------------------------------------------------------------------------
  64.  
  65. ODULong Node::Size() 
  66. {
  67.     ODULong size = 0;
  68.     
  69.     Node* node = this->FirstTopDown();
  70.     while (node)
  71.     {
  72.         size++;
  73.         node = node->NextTopDown(kODFrontToBack);
  74.     }
  75.     return size;
  76. }
  77.  
  78. //------------------------------------------------------------------------------
  79. // Node::GetNextSibling
  80. //
  81. // Description
  82. //------------------------------------------------------------------------------
  83.  
  84. Node* Node::GetNextSibling()
  85. {
  86.     Node* parent = this->GetParent();
  87.     return parent ? parent->GetChildAfter(this) : kODNULL;
  88. }
  89.  
  90. //------------------------------------------------------------------------------
  91. // Node::GetPreviousSibling
  92. //
  93. // Description
  94. //------------------------------------------------------------------------------
  95.  
  96. Node* Node::GetPreviousSibling()
  97. {
  98.     Node* parent = this->GetParent();
  99.     return parent ? parent->GetChildBefore(this) : kODNULL;
  100. }
  101.  
  102. //------------------------------------------------------------------------------
  103. // Node::NextTopDown
  104. //
  105. // Description
  106. //------------------------------------------------------------------------------
  107.  
  108. Node* Node::NextTopDown(ODSiblingOrder siblingOrder)
  109. {
  110.     Node* child;
  111.     if (siblingOrder == kODFrontToBack)
  112.         child = this->GetFirstChild();
  113.     else
  114.         child = this->GetLastChild();
  115.     
  116.     if (child)
  117.         return child;
  118.     else 
  119.     {
  120.         Node* sibling;
  121.         if (siblingOrder == kODFrontToBack)
  122.             sibling = this->GetNextSibling();
  123.         else 
  124.             sibling = this->GetPreviousSibling();
  125.  
  126.         if (sibling) 
  127.             return  sibling;
  128.         else 
  129.             return this->GetNextAunt(siblingOrder);
  130.     }
  131.     return kODNULL;
  132. }
  133.  
  134. //------------------------------------------------------------------------------
  135. // Node::GetNextAunt
  136. //
  137. // Description
  138. //------------------------------------------------------------------------------
  139.  
  140. Node* Node::GetNextAunt(ODSiblingOrder siblingOrder)
  141. {
  142.     Node* parent = this->GetParent();
  143.     
  144.     if (parent)
  145.     {
  146.         Node* sibling;
  147.         if (siblingOrder == kODFrontToBack)
  148.             sibling = parent->GetNextSibling();
  149.         else
  150.             sibling = parent->GetPreviousSibling();
  151.         
  152.         if (sibling) 
  153.             return sibling;
  154.         else 
  155.             return parent->GetNextAunt(siblingOrder);
  156.     }
  157.     else
  158.         return kODNULL;
  159. }
  160.  
  161. //------------------------------------------------------------------------------
  162. // Node::FirstBottomUp
  163. //
  164. // Description
  165. //------------------------------------------------------------------------------
  166.  
  167. Node* Node::FirstBottomUp(ODSiblingOrder siblingOrder)
  168. {
  169.     Node* child;
  170.     if (siblingOrder == kODFrontToBack)
  171.         child = this->GetFirstChild();
  172.     else
  173.         child = this->GetLastChild();
  174.  
  175.     if (child)
  176.         return child->FirstBottomUp(siblingOrder);
  177.     else
  178.         return this;
  179. }
  180.  
  181. //------------------------------------------------------------------------------
  182. // Node::NextBottomUp
  183. //
  184. // Description
  185. //------------------------------------------------------------------------------
  186.  
  187. Node* Node::NextBottomUp(ODSiblingOrder siblingOrder)
  188. {
  189.     Node* parent = this->GetParent();
  190.  
  191.     if (parent)
  192.     {
  193.         Node* sibling;
  194.         if (siblingOrder == kODFrontToBack)
  195.             sibling = parent->GetChildAfter(this);
  196.         else
  197.             sibling = parent->GetChildBefore(this);
  198.         
  199.         if (sibling)
  200.             return sibling->FirstBottomUp(siblingOrder);
  201.         else
  202.             return parent;
  203.     }
  204.     else
  205.         return kODNULL;    
  206.  
  207.     return kODNULL;
  208. }
  209.  
  210. //======================================================================================
  211. // NodeTraverser
  212. //======================================================================================
  213.  
  214. //------------------------------------------------------------------------------
  215. // NodeTraverser::NodeTraverser
  216. //
  217. // Description
  218. //------------------------------------------------------------------------------
  219.  
  220. NodeTraverser::NodeTraverser(Node* root, 
  221.                     ODTraversalType traversalType, 
  222.                     ODSiblingOrder siblingOrder)
  223. {
  224.     fRoot = root;
  225.     fCurrent = kODNULL;
  226.     fTraversalType = traversalType;
  227.     fSiblingOrder = siblingOrder;
  228. }
  229.  
  230. //------------------------------------------------------------------------------
  231. // NodeTraverser::First
  232. //
  233. // Description
  234. //------------------------------------------------------------------------------
  235.  
  236. Node*    NodeTraverser::First()
  237. {
  238.     if (fRoot)
  239.     {
  240.         if (fTraversalType == kODTopDown)
  241.             fCurrent = this->FirstTopDown(fRoot);
  242.         else if (fTraversalType == kODBottomUp)
  243.             fCurrent = this->FirstBottomUp(fRoot,fSiblingOrder);
  244.         else if (fTraversalType == kODChildrenOnly)
  245.         {
  246.             if (fSiblingOrder == kODFrontToBack)
  247.                 fCurrent = fRoot->GetFirstChild();
  248.             else
  249.                 fCurrent = fRoot->GetLastChild();
  250.         }
  251.         return fCurrent;
  252.     }
  253.     else
  254.         return kODNULL;
  255. }
  256.  
  257. //------------------------------------------------------------------------------
  258. // NodeTraverser::Next
  259. //
  260. // Description
  261. //------------------------------------------------------------------------------
  262.  
  263. Node*    NodeTraverser::Next()
  264. {
  265.     if (fCurrent)
  266.     {
  267.         if (fTraversalType == kODTopDown)
  268.             fCurrent = this->NextTopDown(fCurrent, fSiblingOrder);
  269.         else if (fTraversalType == kODBottomUp)
  270.             fCurrent = this->NextBottomUp(fCurrent, fSiblingOrder);
  271.         else if (fTraversalType == kODChildrenOnly)
  272.         {
  273.             if (fSiblingOrder == kODFrontToBack)
  274.                 fCurrent = fCurrent->GetNextSibling();
  275.             else
  276.                 fCurrent = fCurrent->GetPreviousSibling();
  277.         }
  278.         return fCurrent;
  279.     }
  280.     else
  281.         return kODNULL;
  282. }
  283.  
  284. //------------------------------------------------------------------------------
  285. // NodeTraverser::SkipChildren
  286. //
  287. // Description
  288. //------------------------------------------------------------------------------
  289.  
  290. void NodeTraverser::SkipChildren()
  291. {
  292.     Node* next = kODNULL;
  293.     Node* skipTo = kODNULL;
  294.     Node* test = kODNULL;
  295.  
  296.     if (fCurrent)
  297.     {
  298.         if (fTraversalType == kODTopDown)
  299.         {
  300.             if (fSiblingOrder == kODFrontToBack)
  301.                 next = fCurrent->GetNextSibling();
  302.             else
  303.                 next = fCurrent->GetPreviousSibling();
  304.  
  305.             if (!next)
  306.                 next = fCurrent->GetNextAunt(fSiblingOrder);
  307.  
  308.             test = fCurrent;
  309.             while ( test && (test != next) )
  310.             {
  311.                 skipTo = test;
  312.                 test = this->NextTopDown(test, fSiblingOrder);
  313.             }
  314.  
  315.             fCurrent = skipTo;
  316.         }
  317.     }
  318. }
  319.  
  320. //------------------------------------------------------------------------------
  321. // NodeTraverser::NextTopDown
  322. //
  323. // Description
  324. //------------------------------------------------------------------------------
  325.  
  326. Node* NodeTraverser::NextTopDown(Node* node, ODSiblingOrder siblingOrder)
  327. {
  328.     Node* child;
  329.     if (siblingOrder == kODFrontToBack)
  330.         child = node->GetFirstChild();
  331.     else
  332.         child = node->GetLastChild();
  333.     
  334.     if (child)
  335.         return child;
  336.     else if (node != fRoot)
  337.     {
  338.         Node* sibling;
  339.         if (siblingOrder == kODFrontToBack)
  340.             sibling = node->GetNextSibling();
  341.         else 
  342.             sibling = node->GetPreviousSibling();
  343.  
  344.         if (sibling) 
  345.             return  sibling;
  346.         else 
  347.             return this->GetNextAunt(node, siblingOrder);
  348.     }
  349.     return kODNULL;
  350. }
  351.  
  352. //------------------------------------------------------------------------------
  353. // NodeTraverser::GetNextAunt
  354. //
  355. // Description
  356. //------------------------------------------------------------------------------
  357.  
  358. Node* NodeTraverser::GetNextAunt(Node* node, ODSiblingOrder siblingOrder)
  359. {
  360.     Node* parent = node->GetParent();
  361.     
  362.     if (parent && (parent != fRoot))
  363.     {
  364.         Node* sibling;
  365.         if (siblingOrder == kODFrontToBack)
  366.             sibling = parent->GetNextSibling();
  367.         else
  368.             sibling = parent->GetPreviousSibling();
  369.         
  370.         if (sibling) 
  371.             return sibling;
  372.         else 
  373.             return this->GetNextAunt(parent, siblingOrder);
  374.     }
  375.     else
  376.         return kODNULL;
  377. }
  378.  
  379. //------------------------------------------------------------------------------
  380. // NodeTraverser::FirstBottomUp
  381. //
  382. // Description
  383. //------------------------------------------------------------------------------
  384.  
  385. Node* NodeTraverser::FirstBottomUp(Node* node, ODSiblingOrder siblingOrder)
  386. {
  387.     Node* child;
  388.     if (siblingOrder == kODFrontToBack)
  389.         child = node->GetFirstChild();
  390.     else
  391.         child = node->GetLastChild();
  392.  
  393.     if (child)
  394.         return this->FirstBottomUp(child, siblingOrder);
  395.     else
  396.         return node;
  397. }
  398.  
  399. //------------------------------------------------------------------------------
  400. // Node::Node
  401. //
  402. // Description
  403. //------------------------------------------------------------------------------
  404.  
  405. Node* NodeTraverser::NextBottomUp(Node* node, ODSiblingOrder siblingOrder)
  406. {
  407.     if (node == fRoot)
  408.         return kODNULL;
  409.         
  410.     Node* parent = node->GetParent();
  411.  
  412.     if (parent)
  413.     {
  414.         Node* sibling;
  415.         if (siblingOrder == kODFrontToBack)
  416.             sibling = parent->GetChildAfter(node);
  417.         else
  418.             sibling = parent->GetChildBefore(node);
  419.         
  420.         if (sibling)
  421.             return this->FirstBottomUp(sibling, siblingOrder);
  422.         else
  423.             return parent;
  424.     }
  425.     else
  426.         return kODNULL;    
  427.  
  428.     return kODNULL;
  429. }
  430.  
  431.